【题解】 「网络流24题」骑士共存问题 网络流 luoguP3355 | Qiuly's blog!

【题解】 「网络流24题」骑士共存问题 网络流 luoguP3355

Posted on | Edited on | In | Comments:

最大流于最小割的转换。

假设现在棋盘上非障碍的位置全部摆满了骑士，我们拿走 $x$ 个的骑士可以使棋盘上的所有骑士互不冲突，求最小的 $x$.

可以跑匈牙利，也可以跑最大流算法，我选择跑 $Dinic$。

所有编号为奇数的点向源点 $s$ 连边，所有编号为偶数的点向汇点 $t$ ，连边，边权为 $1$.可以知道，同奇偶编号的点是无法互相攻击的，我们将在奇数和偶数之间可以攻击到彼此的点连一条边权无限大的边。

然后跑一遍 $Dinic$ 。

然后就没了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int 
#define ID(i,j) ((i-1)*n+j)
#define A printf("A")
using namespace std;
const int M=5e5+2;
const short dx[8]={1,1,-1,-1,2,2,-2,-2};
const short dy[8]={2,-2,2,-2,1,-1,1,-1};
int n,m,s,t,sum,cnt,dep[M],head[M];
short ok[202][202];
template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}
struct Edge{int nxt,to,val;}G[M];
inline void add(int x,int y,int v){
    G[cnt].to=y,G[cnt].val=v,G[cnt].nxt=head[x],head[x]=cnt++;
    G[cnt].to=x,G[cnt].val=0,G[cnt].nxt=head[y],head[y]=cnt++;
} 
inline bool bfs(){
    memset(dep,-1,sizeof(dep)); 
    queue<int>q;q.push(s);dep[s]=0;
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=head[x];i!=-1;i=G[i].nxt){
		    int y=G[i].to;
			if(dep[y]!=-1||!G[i].val)continue;
			else{dep[y]=dep[x]+1,q.push(y);if(y==t)return true;} 
		} 
    }return false;
} 
inline int dfs(int x,int flow){
    if(x==t||!flow)return flow;
    int used=0,rlow;
    for(int i=head[x];i!=-1;i=G[i].nxt){
        int y=G[i].to;
        if(dep[y]==dep[x]+1&&G[i].val){
            used+=(rlow=dfs(y,min(G[i].val,flow-used)));
            G[i].val-=rlow,G[i^1].val+=rlow;
        }
    }if(!used)dep[x]=-1;
    return used;
}
inline int dinic(){
    int maxlow=0;
    while(bfs())maxlow+=dfs(s,1e9);
	return maxlow; 
}
int main(){
    memset(head,-1,sizeof(head));
    IN(n),IN(m);s=0,t=n*n+1;sum=n*n-m;
    for(int x,y,i=1;i<=m;++i)IN(x),IN(y),ok[x][y]=1;
    for(int i=1;i<=n;++i)
       for(int j=1;j<=n;++j){
           if(ok[i][j])continue;
           if((i+j)&1){
               add(s,ID(i,j),1);
               for(int k=0;k<8;++k){
                   int nx=i+dx[k],ny=j+dy[k];
                   if(nx<1||ny<1||nx>n||ny>n||ok[nx][ny])continue;
                   add(ID(i,j),ID(nx,ny),1e9);
               }
           }else add(ID(i,j),t,1);
       }printf("%d\n",sum-dinic());
    return 0;   
}

本文标题:【题解】 「网络流24题」骑士共存问题 网络流 luoguP3355

文章作者:Qiuly

发布时间:2019年02月15日 - 00:00

最后更新:2019年03月29日 - 13:54

原始链接:http://qiulyblog.github.io/2019/02/15/[题解]luoguP3355/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。